package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 插入区间
 * 2025-03-03 16:21:01
 * 遍历已有区间，通过将已有区间和待插入区间做比较，得到新的区间。
 * 时间复杂度O(n)，空间复杂度O(1)
 */
class InsertInterval {

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;// placed的含义是待插入区间是否被放置
        List<int[]> ansList = new ArrayList<int[]>();
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集，计算它们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        // 将list转换成需要的结果
        return ansList.toArray(new int[ansList.size()][]);
//        int[][] ans = new int[ansList.size()][2];
//        for (int i = 0; i < ansList.size(); ++i) {
//            ans[i] = ansList.get(i);
//        }
//        return ans;
        
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new InsertInterval().new Solution();
        
    }
}